//
//  dynamic.cpp
//  labuladong
//
//  Created by 刘振舟 on 2023/8/2.
//

#include "dynamic.hpp"


int DynamicSolution::coinChange(vector<int> &coins, int amount) { 
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for(int i = 0; i <= amount; ++i) {
        for(int coin : coins) {
            int subProblem = i - coin;
            if (subProblem < 0) {
                continue;
            }
            dp[i] = min(dp[i], 1 + dp[subProblem]);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}